package com.leetcode.array;

import java.util.Arrays;
import java.util.HashSet;

/**
 * @author: ZhouBert
 * @date: 2019/10/9
 * @description: 287. 寻找重复数
 * B-【虽然只有B，但是由于题目中限制条件过多，如果忽视条件，可以头脑风暴，联想出各种问题来解决重复数字问题】
 * 给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
 * <p>
 * 示例 1:
 * 输入: [1,3,4,2,2]
 * 输出: 2
 * 示例 2:
 * 输入: [3,1,3,4,2]
 * 输出: 3
 * <p>
 * 说明：
 * 不能更改原数组（假设数组是只读的）。
 * 只能使用额外的 O(1) 的空间。
 * 时间复杂度小于 O(n2) 。
 * 数组中只有一个重复的数字，但它可能不止重复出现一次。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-the-duplicate-number
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * <p>
 * [LeetCode 0287] Find the Duplicate Number [OTTFF]
 * https://www.bilibili.com/video/av62810942?from=search&seid=11192535059340662906
 */
public class FindDuplicate287Awesome {

	/**
	 * todo:暴力解法：Time[O(n2)]	Space[O(1)]
	 * 119 ms-8%;37.4 MB-93.77%
	 * 双重循环，依次将每个元素与剩下的元素判断是否出现重复
	 *
	 * @param nums
	 * @return
	 */
	public static int findDuplicateByBF(int[] nums) {
		int len = nums.length;
		for (int i = 0; i < len; i++) {
			for (int j = i + 1; j < len; j++) {
				if (nums[i] == nums[j]) {
					return nums[i];
				}
			}
		}
		return -1;
	}

	/**
	 * todo:HashSet 解法：Time[O(n)]	Space[O(n)]
	 * 5 ms-56.05%;38 MB-83.24%
	 *
	 * @return
	 */
	public static int findDuplicateByHashSet(int[] nums) {
		HashSet<Integer> hashSet = new HashSet<>();
		for (Integer item :
				nums) {
			if (hashSet.contains(item)) {
				return item;
			} else {
				hashSet.add(item);
			}
		}
		return -1;
	}

	/**
	 * todo:Hash 字符哈希：Time[O(n)]	Space[O(n)]
	 * 1 ms-96.83%;37.3 MB-94.18%
	 * todo:卧槽，数组比 hashSet 简单多了
	 *
	 * @param nums
	 * @return
	 */
	public static int findDuplicateByHash(int[] nums) {
		///1.定义一个新列表，遍历元素放入数组中，空下一个0的位置，因为
		int[] arr = new int[nums.length + 1];

		for (int i = 0; i < nums.length; i++) {
			if (arr[nums[i]] != 0) {
				return nums[i];
			} else {
				arr[nums[i]] = 1;
			}
		}
		return -1;
	}

	/**
	 * todo:负数标记法（从评论区找到对应方法）【】
	 * 负数标记法有点没看懂，先放着...
	 * 还有个异或的方法也没有看懂
	 *
	 * @param nums
	 * @return
	 */
	public static int findDuplicateByMinus(int[] nums) {
		int i = 0;
		while (true) {
			int val = nums[i];
			if (val > 0) {
				nums[i] = -nums[i];
				i=val;
			}else {
				return i;
			}
		}
	}

	/**
	 * todo：FirstMissingPositive41 很像【】
	 *
	 * @param nums
	 * @return
	 */
	public static int findDuplicateByMissingPositiveWay(int[] nums) {
		int index = 0;
		while (index < nums.length) {
			int curVar = nums[index];
			if (curVar == index + 1) {
				index++;
				continue;
			}
			while (curVar != index + 1) {
				int nextVar = nums[curVar - 1];
				if (nextVar == curVar) {
					return curVar;
				}
				nums[curVar - 1] = curVar;
				curVar = nextVar;
			}
			nums[index++] = curVar;
		}
		return -1;
	}

	/**
	 * todo:先排序，然后比较相邻值 Time[O(n)]	Space[O(n)]
	 * 4ms-62.38%
	 *
	 * @param nums
	 * @return
	 */
	public static int findDuplicateByOrderArray(int[] nums) {
		///1.对数组进行排序
		Arrays.sort(nums);
		///2.遍历，比较当前节点和后一个节点是否相同
		for (int i = 1; i < nums.length; i++) {
			if (nums[i - 1] == nums[i]) {
				return nums[i - 1];
			}
		}
		return -1;
	}


	/**
	 * todo:通过二分法【】
	 *
	 * @param nums
	 * @return
	 */
	public static int findDuplicateByDivision(int[] nums) {
		int left = 0;
		int right = nums.length - 1;
		while (left < right) {
			int mid = left + (right - left) / 2;
			int count = 0;
			///计算小于等于平均值的个数
			for (int num : nums) {
				if (num <= mid) {
					count++;
				}
			}

			if (count <= mid) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}
		return right;
	}

	/**
	 * todo:通过异或。感觉跟高斯求和类似--但是我还是解错了
	 * 6ms
	 * 在我的理解中，用n+1-num[i] 去异或。--是有问题的，不确定重复的数值是在 halfN 上还是下
	 * 卧槽，原来是先经过排序，然后再用 异或的方式 代替 比较是否相等。但是这个不仅仅是异或，还需要跟0进行比较。
	 * @return
	 */
	public static int findDuplicateByXOR(int[] nums) {
		///wrong
//		int n = nums.length;
//		int halfN = n / 2;
//
//		int temp = 0;
//		for (int i = 0; i < n; i++) {
//			if (nums[i] > halfN) {
//				temp ^= (n - nums[i]);
//			} else {
//				temp ^= (nums[i]);
//			}
//		}
//		return temp;

		Arrays.sort(nums);
		for (int i = 0; i < nums.length-1; i++) {
			if ((nums[i]^nums[i+1]) == 0){
				return nums[i];
			}
		}
		return -1;
	}


	/**
	 * todo:通过快慢指针的方法【】
	 *
	 * 0ms
	 * @return
	 */
	public static int findDuplicateByCircleList(int[] nums){
		int fast=nums[0],slow=fast;
		///1,查找相遇点
		do {
			///2.下一个 slow 的点即
			slow=nums[slow];
			///3.下下一个节点
			fast=nums[nums[fast]];
		}while (fast!=slow);

		///4.查找环形的第一个
		int begin=nums[0];
		while (begin!=slow){
			begin=nums[begin];
			slow=nums[slow];
		}
		return slow;
	}

	/**
	 * Fail.todo:将所有数相加，减去sum(1~n)---这个不适合多个重复的情况！
	 *
	 * @return
	 */
	public static int findDuplicateByMath(int[] nums) {
		int len = nums.length;
		int sum = 0, sumn = 0;
		///原来公有n+1个数
		for (int i = 0; i < len; i++) {
			sum += nums[i];
			sumn += i;
		}
		return sum - sumn;
	}




	public static void main(String[] args) {
		int[] nums = new int[]{1, 3, 4, 2, 2};
		System.out.println(findDuplicateByXOR(nums));
		///将1和2 求异或
		System.out.println(1 ^ 2 ^ 3 ^ 4 ^ 2);
		///异或：(1+n)=5; 1, 2, 1, 2, 2
		System.out.println(1 ^ 1 ^ 0 ^ 2 ^ 2);
		System.out.println(0 ^ 2);
	}

}
